//
// Created by WQM on 2020/10/8.
//
/**
 *     二叉树
 *          二叉链表
 *
 *     三叉链表
 *     ***********
 *     树和森林
 *          孩子链表示法 ，孩子兄弟链表示法和双亲标识法
 *
 */



#include "LKQueue.h"

#ifndef TEST_BINTREE_H
#define TEST_BINTREE_H

#endif //TEST_BINTREE_H
/**
 * 二叉链表
 *  1 initBinTree(BinTree bt)
 *  8 EnBinTree(BinTree bt,DataType d,int Position)  入树
 *  2 EmptyBinTree(BinTree bt)
 *  3 VisitBinTreee(BinTree bt)
 *  4 PreOrder
 *  5 InOrder
 *  6 PostOrder
 *  7 int BinTreeHeigth 求二叉树的高度
 * */
typedef struct btnode {
    DataType data;
    struct btnode *lchild, *rchild;
} *BinTree;

//1
BinTree initBinTree(BinTree bt) {
    bt = malloc(sizeof(BinTree));
    DataType temp;
    bt->data = temp;
    bt->rchild = NULL;
    bt->lchild = NULL;
    return bt;
}

/**
 * 8 入树
 * int postion : 0 添加到左子树中 1 添加到右子树中，默认0
 * */
BinTree EnBinTree(BinTree bt, DataType d, int Position) {

    BinTree new = malloc(sizeof(BinTree));
    new->data = d;
    new->rchild = NULL;
    new->lchild = NULL;
    switch (Position) {
        case 0 :
            bt->data = d;
            return bt;
        case -1:
            bt->lchild = new;
            printf("add left child\n");
            return bt;
        case 1:
            bt->rchild = new;
            printf("add right child\n");
            return bt;
    }
}

//2
int EmptyBinTree(BinTree bt) {
    if (bt != NULL) {
        printf("非空二叉树\n");
        return 0;
    } else {
        printf("空二叉树\n");
        return 1;
    }
}

//3
void VisitBinTreee(BinTree bt) {
    if (bt != NULL) {
        printf("%s\n", bt->data.name);
    }else{
        printf("bt is __\n");
    }

}

//4 先序遍历
void PreOrder(BinTree bt) {
    if (bt != NULL) {
        VisitBinTreee(bt);    //访问根节点
        PreOrder(bt->lchild); //先序遍历左子树
        PreOrder(bt->rchild);//先序遍历右子树
    } else printf("空\n");
}

//5 中序遍历
void InOrder(BinTree bt) {
    if (bt != NULL) {
        InOrder(bt->lchild);
        VisitBinTreee(bt);
        InOrder(bt->rchild);
    }
}

//6 后序遍历
void PostOrder(BinTree bt) {
    if (bt != NULL) {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        VisitBinTreee(bt);
    }
}

//7 求二叉树的高度
int BinTreeHeigth(BinTree bt) {
    int lh, rh;
    if (bt == NULL)return 0;
    else {
        lh = BinTreeHeigth(bt->lchild);        //左子树高度
        rh = BinTreeHeigth(bt->rchild);        //右子树的高度
        return 1 + (lh > rh ? lh : rh);
    }
}

//8 层次遍历
//int levelOrder(BinTree bt) {
//    // 建立使用一个队列 保证做进右出 根节点 做孩子 有孩子 进队列
//    LKQue Q;
//    DataType P;
//    if (bt != NULL) {
//        EnLKQue(Q, bt->data);
//        while (!EmptyLKQue(Q)) {
//            P = GetHead(Q);
//            OutLKQue(Q);
//            VisitBinTreee(P);
//            if (p->lchild != NULL) EnLKQue(Q, P->lchild);//左孩子结点入队列
//            if (p->rchild != NULL) EnLKQue(Q, P->rchild);//右孩子结点入队列
//        }
//    }
//
//}
//TODO 非递归实现 先序遍历
//TODO 构造二叉树（p110）
/**
 * 三叉链表
 * */
typedef struct ttnode {
    DataType data;
    struct ttnode *parrent, *lchild, *rchild;
} *TBinTree;
/***********************************************************************************************************************/
/**
 * 树的常用三种存储结构
 * 1 孩子连标识法
 * 2 孩子兄弟链表示法
 * 3 双亲表示法
 * */

/**
 * 1 孩子连标识法
 * */
const int MAXND = 20;      //树种最大节点数
/*表结点类型*/
typedef struct bnode {       //表节点类型
    int child;              //孩子节点在头表头数据组中的序号
    struct bnode *next;     //表结点指针
} node, *childlink;
/*不带双亲*/
typedef struct {
    DataType data;
    childlink hp;
} headnode;
/*带双亲的*/
typedef struct {
    DataType data;
    int parent;
    childlink hp;
} headnode_with_parent;
headnode link[MAXND];
/**
 * 2 孩子兄弟链表示法
 * */
typedef struct tnode {
    DataType data;
    struct tnode *son, *brother;  //指向孩子和兄弟的指针
} *Tree;
/**
 * 3 双亲表示法
 * */
typedef struct {
    DataType data;
    int parent;
} Node_parent;
Node_parent slist[MAXND];